package leetcode1;

public class Day1 {
    public static void main(String[] args) {
        int[] nums = {6,7,1,2};
        //increasingTriplet(nums);
    }

    //300.最长递增子序列--贪心法
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] map = new int[n];
        map[0]=nums[0];
        int border=0,len=1;
        for(int i=1;i<n;i++) {
            //处理边界情况
            if(nums[i]>map[border]) {
                map[++border]=nums[i];
                len++;
                continue;
            }
            //寻找存放nums[i]的位置（在>=nums[i]的值中找到最小的那个值，用来替换nums[i]）
            int left=0,right=border;
            while(left<right) {
                int mid = (left+right)/2;
                if(map[mid] < nums[i]) left=mid+1;
                else right=mid;
            }
            map[right]=nums[i];
        }
        return len;
    }
    //334.递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int[] map = new int[3];
        map[0]=nums[0];
        int border=0,len=1;
        for(int i=1;i<n;i++) {
            //处理边界情况
            if(nums[i]>map[border]) {
                map[++border]=nums[i];
                len++;
                if(len>=3) return true;
                continue;
            }
            //存在比nums[i]大的位置
            for(int j=0;j<len;j++) {
                if(map[j]>=nums[i]){
                    map[j]=nums[i];
                    break;
                }
            }
        }
        return false;
    }

}
